#define _CRT_SECURE_NO_WARNINGS 1

#include "BT.h"

BTNode* BuyNewNode(BTDataType x)
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (tmp == NULL)
	{
		perror("malloc fail!");
		return;
	}
	tmp->_data = x;
	tmp->_left = NULL;
	tmp->_right = NULL;
	return tmp;
}

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi]=='#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* cur = BuyNewNode(a[*pi]);
	(*pi)++;
	cur->_left = BinaryTreeCreate(a, n, pi);
	cur->_right = BinaryTreeCreate(a, n, pi);
	return cur;
}

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
	*root = NULL;
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int right = BinaryTreeSize(root->_left);
	int left = BinaryTreeSize(root->_right);
	return 1 + right + left;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
	int left = BinaryTreeLeafSize(root->_left);
	int right = BinaryTreeLeafSize(root->_right);
	return left + right;
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	int left = BinaryTreeLevelKSize(root->_left, k - 1);
	int right = BinaryTreeLevelKSize(root->_right, k - 1);
	return left + right;
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* left = BinaryTreeFind(root->_left, x);
	BTNode* right = BinaryTreeFind(root->_right, x);
	if (left == NULL && right == NULL)
	{
		return NULL;
	}
	else if (right == NULL)
	{
		return left;
	}
	else
	{
		return right;
	}
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("%c", '#');
		return;
	}
	printf("%c", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("%c", '#');
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c", root->_data);
	BinaryTreeInOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("%c", '#');
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c", root->_data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu;
	BTNode* cur;
	QueueInit(&qu);
	QueuePush(&qu, root);
	while (!QueueEmpty(&qu))
	{
		cur = QueueFront(&qu);
		printf("%c", cur->_data);
		if (cur->_left)
		{
			QueuePush(&qu, cur->_left);
		}
		if (cur->_right)
		{
			QueuePush(&qu, cur->_right);
		}
		QueuePop(&qu);
	}
	QueueDestroy(&qu);
}

int BinaryTreeComplete(BTNode* root)
{
	Queue qu;
	BTNode* cur;
	QueueInit(&qu);
	QueuePush(&qu, root);
	while (!QueueEmpty(&qu))
	{
		cur = QueueFront(&qu);
		QueuePop(&qu);
		if (cur == NULL)
		{
			break;
		}
		QueuePush(&qu, cur->_left);
		QueuePush(&qu, cur->_right);
	}

	while (!QueueEmpty(&qu))
	{
		cur = QueueFront(&qu);
		QueuePop(&qu);
		if (cur != NULL)
		{
			QueueDestroy(&qu);
			return 0;
		}
	}
	return 1;
	QueueDestroy(&qu);
}